//============================================================================
// Name        : radix-sort.cpp
// Author      : Abram Gutierrez
// Date        : 9/29/11
// Copyright   : credit to lecture slides and TAs
// Description : Implementation of radix sort in C++
//============================================================================

#include "sort.h"
#include <iostream>
#include <cmath>
using namespace std;

void RadixSort::sort(int A[], int size)
{
	int base = 10, r; 
	int digit = 7;	//will sort number up to 7 digits
	int *B = new int[size];
	int *C = new int[base];
	
	for(int m = 0; m < digit; m++) //based on counting sort
	{
		for(int i = 0; i < base; ++i) C[i] = 0; //initialize array elements to 0
		for(int j = 0; j < size; ++j) 
		{
			r = (A[j] / (int)(pow(10.0,m))) % base; //find the value of the digit
			++C[r];
		}
		for(int i = 1; i < base; ++i) C[i] += C[i-1];
		for(int j = size-1; j >= 0; --j)
		{
			r = (A[j] / (int)(pow(10.0,m))) % base;
			int i = --C[r];
			B[i] = A[j];
		}
		for(int j = 0; j < size; ++j) A[j] = B[j];
	}
	delete(B);
	delete(C);
}
